const int maxn = 1000000 + 5;

char s[maxn], t[maxn * 2];
int len[maxn * 2];

void manacher() {
  int n = strlen(s) * 2 + 1;
  for (int i = 0; i < n; ++i) t[i] = (i & 1 ? s[i / 2] : '#');
  int l = 0, r = -1;
  for (int i = 0; i < n; i++) {
    int k = (i > r) ? 1 : min(len[l + r - i], r - i);
    while (0 <= i - k && i + k < n && t[i - k] == t[i + k]) k++;
    len[i] = --k;
    if (i + k > r) l = i - k, r = i + k;
  }
  for (int i = 1; i < n - 1; ++i) {
    int l = (i - len[i] + 1) / 2,
        r = (i + len[i] - 1) / 2;
    // s[l..r] is a maximal palindromic substring
  }
}
